// https://www.lintcode.com/problem/sqrtx-ii/description

class Solution {
public:
    /**
     * @param x: a double
     * @return: the square root of x
     */
    // 不是按整数，复杂度不是logn
    // L / 2^x <= 10^(-t) => x >= log2(L) + tlog2(10)
    double sqrt(double x) {
        double low = 0;
        // double high = x; 注意小于1的情况
        double high = max(x, 1.0); 
        double eps = 1e-10; // 这个精度是自己设的，不一定能满足精度，所以只好二分时候尽量让一边更靠近答案，最后返回那一边！
        // while (low + 1 < high) {
        while (low + eps < high) {
            double mid = (high - low) / 2 + low;
            double res = mid * mid;
            // if (abs(res - x) < eps) {
                // return mid;
            if(res < x) {
                low = mid;
            } else {
                high = mid;
            }
        }
        // if (abs(low * low - x) < eps) {
        //     return low;
        // } else {
        //     return high;
        // }
        return low;
    }
    
    // double sqrt(double x) {
    //     // Write your code here
    //     double left = 0.0;
    //     double right = x;
    //     double eps = 1e-12;

    //     if(right < 1.0) {
    //         right = 1.0;
    //     }

    //     while(right - left > eps) {
    //         double mid = (right + left) / 2;
    //         if(mid * mid < x) {
    //             left = mid;
    //         }
    //         else {
    //             right = mid;
    //         }
    //     }

    //     return left;
    // }
};